#include <stdlib.h>
#include <string.h>

#include "object.h"
#include "memory.h"
#include "dict.h"

struct Listnode_struct { 
    struct Listnode_struct *next;
	struct Listnode_struct *last;
	void * value; 
	void * key;
	int value_owned;
}; 

typedef struct Listnode_struct * Listnode;

struct List_struct {
	Listnode 	head;
	Listnode 	tail;
	Objectinfo	info;
}; 

typedef struct List_struct * List;

List list_make(Objectinfo info) {
	List result = memory_make(List);
	result->head = NULL;
	result->tail = NULL;
	result->info = info;
	return result;
}

Listnode listnode_make(void *data, Objectinfo info) {
	void * newdata 		= info->copy(data);
	Listnode result 	= memory_make(Listnode);
	result->value   	= newdata;
	result->value_owned = 1;
	result->next        = result->last = NULL;
	return result;
}

List list_insert_node(List self, Listnode newnode, Listnode left )   { 
	if(!left) {	
		left = self->tail;
	}
	
	newnode->last     = left;
	
	if(left)	{ 
		newnode->next = left->next;  
		left->next    = newnode;
	}
	else 	{ 
		self->head    = newnode; 		
	}
	/* If the tail is null, the list was empty. */
	if(newnode->next) {
		newnode->next->last	= newnode;
	} else {
		self->tail   	= newnode;
	}
	return self;
}  

List list_insert(List self, void * value, Listnode after) {
	Listnode newnode = listnode_make(value, self->info);
	return list_insert_node(self, newnode, after);
} 


List list_add(List self, void * value) {
	return list_insert(self, value, NULL);
} 


List list_remove_node(List self, Listnode node)   { 	
 	if(!node) return NULL;
    if(node->next) { 
      node->next->last	= node->last;
	} else {    
		self->tail		= node->last;
 	}
    if(node->last) {
      node->last->next	= node->next;
	} else { 
      self->head 		= node->next;
    }
	return self;
}  



struct Hashmapentry_struct {
   struct UT_hash_table *tbl;
   void 		*key;
   void 		*value;                    
   Objectinfo 	*value_info;
   void 		*last;  
   void 		*next;  
   struct Hashmapentry_struct *last_entry;   
   struct Hashmapentry_struct *next_entry;    
};

typedef struct Hashmapentry_struct * Hashmapentry;

struct Hashmapbucket_struct {
   Hashmapentry * entries;
   int count;  
   int expand_mult;  
};

typedef struct Hashmapbucket_struct * Hashmapbucket; 



struct Hashmap_struct  {
   Hashmapbucket buckets;
   int num_buckets;
   int num_items;
   int noexpand;  /* when set, inhibits expansion of buckets for this hash  */
   double hash_q; /* measures the evenness of the items among buckets (0-1) */
   Hashmapentry head;
   Hashmapentry tail; 
   Hashmapentry next;    
   Objectinfo 	*key_info;

   unsigned bkt_i, bkt_ideal, sum_of_deltas;
   double new_hash_q;
   
};

typedef struct Hashmap_stuct * Hashmap;

#ifdef _NO_WAY

void * hashmap_find(Hashmap self, void *key) {                         
	Hashmapbucket aid = self->head;
	if(self->head) { 
		long hash = self->key_info->hash(key);
		
     HASH_FIND_IN_BKT(hh, (head)->hh.tbl->buckets[ (head)->hh.tbl->bkt], \
             keyptr,keylen_in,out);                                      \
  }                                                                      \
} 


static void* hashmap_find_in_bucket(Hashmap self, Hashmapbucket bucket, void *key) { 
	Hashmapentry aid   = (head.hh_head) ? (head.hh_head->elmt) : NULL;             
	     
while (out) {                                                        \
    if (out->hh.keylen == keylen_in) {                               \
        if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \
    }                                                                \
    out= (out->hh.hh_next) ? (out->hh.hh_next->elmt) : NULL;         \
}

#endif


#ifndef UTHASH_H
#define UTHASH_H 

#define uthash_fatal(msg) exit(-1)        /* fatal error (out of memory,etc) */
#define uthash_bkt_malloc(sz) malloc(sz)  /* malloc fcn for UT_hash_bucket's */
#define uthash_bkt_free(ptr) free(ptr)    /* free fcn for UT_hash_bucket's   */
#define uthash_tbl_malloc(sz) malloc(sz)  /* malloc fcn for UT_hash_table    */
#define uthash_tbl_free(ptr) free(ptr)    /* free fcn for UT_hash_table      */

#define uthash_noexpand_fyi(tbl)          /* can be defined to log noexpand  */
#define uthash_expand_fyi(tbl)            /* can be defined to log expands   */

/* initial number of buckets */
#define HASH_INITIAL_NUM_BUCKETS 32  /* initial number of buckets        */
#define HASH_BKT_CAPACITY_THRESH 10  /* expand when bucket count reaches */

#define HASH_FIND(hh,head,keyptr,keylen_in,out)                          \
do {                                                                     \
  out=head;                                                              \
  if (head) {                                                            \
     (head)->hh.tbl->key = (char*)(keyptr);                              \
     (head)->hh.tbl->keylen = keylen_in;                                 \
     HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen,                \
             (head)->hh.tbl->num_buckets,(head)->hh.tbl->bkt,            \
             (head)->hh.tbl->i, (head)->hh.tbl->j,(head)->hh.tbl->k);    \
     HASH_FIND_IN_BKT(hh, (head)->hh.tbl->buckets[ (head)->hh.tbl->bkt], \
             keyptr,keylen_in,out);                                      \
  }                                                                      \
} while (0)

#define HASH_ADD(hh,head,fieldname,keylen_in,add)                        \
        HASH_ADD_KEYPTR(hh,head,&add->fieldname,keylen_in,add)
 
#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add)                    \
do {                                                                     \
 add->hh.next = NULL;                                                    \
 add->hh.key = (char*)keyptr;                                            \
 add->hh.keylen = keylen_in;                                             \
 add->hh.elmt = add;                                                     \
 if (!(head)) {                                                          \
    head = add;                                                          \
    (head)->hh.prev = NULL;                                              \
    (head)->hh.tbl = (UT_hash_table*)uthash_tbl_malloc(                  \
                    sizeof(UT_hash_table));                              \
    if (!((head)->hh.tbl))  { uthash_fatal( "out of memory"); }          \
    (head)->hh.tbl->name = #head;                                        \
    (head)->hh.tbl->tail = &(add->hh);                                   \
    (head)->hh.tbl->noexpand = 0;                                        \
    (head)->hh.tbl->hash_q = 1;                                          \
    (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS;              \
    (head)->hh.tbl->num_items = 0;                                       \
    (head)->hh.tbl->hho = ((long)(&add->hh) - (long)(add));              \
    (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_bkt_malloc(        \
            HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket));     \
    if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); }   \
    memset((head)->hh.tbl->buckets, 0,                                   \
            HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket));     \
 } else {                                                                \
    (head)->hh.tbl->tail->next = add;                                    \
    add->hh.prev = (head)->hh.tbl->tail->elmt;                           \
    (head)->hh.tbl->tail = &(add->hh);                                   \
 }                                                                       \
 (head)->hh.tbl->num_items++;                                            \
 add->hh.tbl = (head)->hh.tbl;                                           \
 (head)->hh.tbl->key = (char*)keyptr;                                    \
 (head)->hh.tbl->keylen = keylen_in;                                     \
 HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen,                    \
         (head)->hh.tbl->num_buckets,                                    \
         (head)->hh.tbl->bkt,                                            \
         (head)->hh.tbl->i, (head)->hh.tbl->j, (head)->hh.tbl->k );      \
 HASH_ADD_TO_BKT(hh,(head)->hh.tbl->buckets[(head)->hh.tbl->bkt],add);   \
 HASH_EMIT_KEY(hh,head,keyptr,keylen_in);                                \
 HASH_FSCK(head);                                                        \
} while(0)

#define HASH_DELETE(hh,head,delptr)                                      \
do {                                                                     \
    if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) )  { \
        uthash_bkt_free((head)->hh.tbl->buckets );                       \
        uthash_tbl_free((head)->hh.tbl);                                 \
        head = NULL;                                                     \
    } else {                                                             \
        if ((delptr) == (head)->hh.tbl->tail->elmt) {                    \
            (head)->hh.tbl->tail = (void*)(((long)((delptr)->hh.prev)) + \
                                           (head)->hh.tbl->hho);         \
        }                                                                \
        if ((delptr)->hh.prev) {                                         \
            ((UT_hash_handle*)(((long)((delptr)->hh.prev)) +             \
                    (head)->hh.tbl->hho))->next = (delptr)->hh.next;     \
        } else {                                                         \
            head = (delptr)->hh.next;                                    \
        }                                                                \
        if ((delptr)->hh.next) {                                         \
            ((UT_hash_handle*)(((long)((delptr)->hh.next)) +             \
                    (head)->hh.tbl->hho))->prev = (delptr)->hh.prev;     \
        }                                                                \
        (head)->hh.tbl->key = (char*)((delptr)->hh.key);                 \
        (head)->hh.tbl->keylen = (delptr)->hh.keylen;                    \
        HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen,             \
                (head)->hh.tbl->num_buckets,(head)->hh.tbl->bkt,         \
                (head)->hh.tbl->i,(head)->hh.tbl->j,(head)->hh.tbl->k ); \
        HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[(head)->hh.tbl->bkt], \
                delptr);                                                 \
        (head)->hh.tbl->num_items--;                                     \
    }                                                                    \
    HASH_FSCK(head);                                                     \
} while (0)


/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */
#define HASH_FIND_STR(head,findstr,out)                                 \
    HASH_FIND(hh,head,findstr,strlen(findstr),out)
#define HASH_ADD_STR(head,strfield,add)                                 \
    HASH_ADD(hh,head,strfield,strlen(add->strfield),add)
#define HASH_FIND_INT(head,findint,out)                                 \
    HASH_FIND(hh,head,findint,sizeof(int),out)
#define HASH_ADD_INT(head,intfield,add)                                 \
    HASH_ADD(hh,head,intfield,sizeof(int),add)
#define HASH_DEL(head,delptr)                                           \
    HASH_DELETE(hh,head,delptr)

/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined.
 * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined.
 * This function misuses fields in UT_hash_table for its bookkeeping variables.
 */
#ifdef HASH_DEBUG
#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0)
#define HASH_FSCK(head)                                                  \
do {                                                                     \
    if (head) {                                                          \
        (head)->hh.tbl->keylen = 0;   /* item counter */                 \
        for(    (head)->hh.tbl->bkt_i = 0;                               \
                (head)->hh.tbl->bkt_i < (head)->hh.tbl->num_buckets;     \
                (head)->hh.tbl->bkt_i++)                                 \
        {                                                                \
            (head)->hh.tbl->bkt_ideal = 0; /* bkt item counter */        \
            (head)->hh.tbl->hh =                                         \
            (head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].hh_head;      \
            (head)->hh.tbl->key = NULL;  /* hh_prev */                   \
            while ((head)->hh.tbl->hh) {                                 \
               if ((head)->hh.tbl->key !=                                \
                   (char*)((head)->hh.tbl->hh->hh_prev)) {               \
                   HASH_OOPS("invalid hh_prev %x, actual %x\n",          \
                    (head)->hh.tbl->hh->hh_prev,                         \
                    (head)->hh.tbl->key );                               \
               }                                                         \
               (head)->hh.tbl->bkt_ideal++;                              \
               (head)->hh.tbl->key = (char*)((head)->hh.tbl->hh);        \
               (head)->hh.tbl->hh = (head)->hh.tbl->hh->hh_next;         \
            }                                                            \
            (head)->hh.tbl->keylen +=  (head)->hh.tbl->bkt_ideal;        \
            if ((head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].count     \
               !=  (head)->hh.tbl->bkt_ideal) {                          \
               HASH_OOPS("invalid bucket count %d, actual %d\n",         \
                (head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].count,    \
                (head)->hh.tbl->bkt_ideal);                              \
            }                                                            \
        }                                                                \
        if ((head)->hh.tbl->keylen != (head)->hh.tbl->num_items) {       \
            HASH_OOPS("invalid hh item count %d, actual %d\n",           \
                (head)->hh.tbl->num_items, (head)->hh.tbl->keylen );     \
        }                                                                \
        /* traverse hh in app order; check next/prev integrity, count */ \
        (head)->hh.tbl->keylen = 0;   /* item counter */                 \
        (head)->hh.tbl->key = NULL;  /* app prev */                      \
        (head)->hh.tbl->hh =  &(head)->hh;                               \
        while ((head)->hh.tbl->hh) {                                     \
           (head)->hh.tbl->keylen++;                                     \
           if ((head)->hh.tbl->key !=(char*)((head)->hh.tbl->hh->prev)) {\
              HASH_OOPS("invalid prev %x, actual %x\n",                  \
                    (head)->hh.tbl->hh->prev,                            \
                    (head)->hh.tbl->key );                               \
           }                                                             \
           (head)->hh.tbl->key = (head)->hh.tbl->hh->elmt;               \
           (head)->hh.tbl->hh = ( (head)->hh.tbl->hh->next ?             \
             (UT_hash_handle*)((long)((head)->hh.tbl->hh->next) +        \
                               (head)->hh.tbl->hho)                      \
                                 : NULL );                               \
        }                                                                \
        if ((head)->hh.tbl->keylen != (head)->hh.tbl->num_items) {       \
            HASH_OOPS("invalid app item count %d, actual %d\n",          \
                (head)->hh.tbl->num_items, (head)->hh.tbl->keylen );     \
        }                                                                \
    }                                                                    \
} while (0)
#else
#define HASH_FSCK(head) 
#endif

/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to 
 * the descriptor to which this macro is defined for tuning the hash function.
 * The app can #include <unistd.h> to get the prototype for write(2). */
#ifdef HASH_EMIT_KEYS
#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)                           \
    (head)->hh.tbl->keylen = fieldlen;                                   \
    write(HASH_EMIT_KEYS, &((head)->hh.tbl->keylen), sizeof(int));       \
    write(HASH_EMIT_KEYS, keyptr, fieldlen);          
#else 
#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)                    
#endif

/* default to Jenkins unless specified e.g. DHASH_FUNCTION=HASH_SAX */
#ifdef HASH_FUNCTION 
#define HASH_FCN HASH_FUNCTION
#else
#define HASH_FCN HASH_JEN
#endif

/* The Bernstein hash function, used in Perl prior to v5.6 */
#define HASH_BER(key,keylen,num_bkts,bkt,i,j,k)                        \
  bkt = 0;                                                             \
  while (keylen--)  bkt = (bkt * 33) + *key++;                         \
  bkt &= (num_bkts-1);          


/* SAX/FNV/OAT/JEN/JSW hash functions are macro variants of those listed at 
 * http://eternallyconfuzzled.com/tuts/hashing.html (thanks Julienne Walker) */
#define HASH_SAX(key,keylen,num_bkts,bkt,i,j,k)                        \
  bkt = 0;                                                             \
  for(i=0; i < keylen; i++)                                            \
      bkt ^= (bkt << 5) + (bkt >> 2) + key[i];                         \
  bkt &= (num_bkts-1);          

#define HASH_FNV(key,keylen,num_bkts,bkt,i,j,k)                        \
  bkt = 2166136261UL;                                                  \
  for(i=0; i < keylen; i++)                                            \
      bkt = (bkt * 16777619) ^ key[i];                                 \
  bkt &= (num_bkts-1);
 
#define HASH_OAT(key,keylen,num_bkts,bkt,i,j,k)                        \
  bkt = 0;                                                             \
  for(i=0; i < keylen; i++) {                                          \
      bkt += key[i];                                                   \
      bkt += (bkt << 10);                                              \
      bkt ^= (bkt >> 6);                                               \
  }                                                                    \
  bkt += (bkt << 3);                                                   \
  bkt ^= (bkt >> 11);                                                  \
  bkt += (bkt << 15);                                                  \
  bkt &= (num_bkts-1);

#define HASH_JEN_MIX(a,b,c)                                            \
{                                                                      \
  a -= b; a -= c; a ^= ( c >> 13 );                                    \
  b -= c; b -= a; b ^= ( a << 8 );                                     \
  c -= a; c -= b; c ^= ( b >> 13 );                                    \
  a -= b; a -= c; a ^= ( c >> 12 );                                    \
  b -= c; b -= a; b ^= ( a << 16 );                                    \
  c -= a; c -= b; c ^= ( b >> 5 );                                     \
  a -= b; a -= c; a ^= ( c >> 3 );                                     \
  b -= c; b -= a; b ^= ( a << 10 );                                    \
  c -= a; c -= b; c ^= ( b >> 15 );                                    \
}

#define HASH_JEN(key,keylen,num_bkts,bkt,i,j,k)                        \
  bkt = 0xfeedbeef;                                                    \
  i = j = 0x9e3779b9;                                                  \
  k = keylen;                                                          \
  while (k >= 12) {                                                    \
     i += (key[0] + ( (unsigned)key[1] << 8 )                          \
       + ( (unsigned)key[2] << 16 )                                    \
       + ( (unsigned)key[3] << 24 ) );                                 \
     j += (key[4] + ( (unsigned)key[5] << 8 )                          \
       + ( (unsigned)key[6] << 16 )                                    \
       + ( (unsigned)key[7] << 24 ) );                                 \
   bkt += (key[8] + ( (unsigned)key[9] << 8 )                          \
       + ( (unsigned)key[10] << 16 )                                   \
       + ( (unsigned)key[11] << 24 ) );                                \
                                                                       \
     HASH_JEN_MIX(i, j, bkt);                                          \
                                                                       \
     key += 12;                                                        \
     k -= 12;                                                          \
  }                                                                    \
  bkt += keylen;                                                       \
  switch ( k ) {                                                       \
     case 11: bkt += ( (unsigned)key[10] << 24 );                      \
     case 10: bkt += ( (unsigned)key[9] << 16 );                       \
     case 9:  bkt += ( (unsigned)key[8] << 8 );                        \
     case 8:  j += ( (unsigned)key[7] << 24 );                         \
     case 7:  j += ( (unsigned)key[6] << 16 );                         \
     case 6:  j += ( (unsigned)key[5] << 8 );                          \
     case 5:  j += key[4];                                             \
     case 4:  i += ( (unsigned)key[3] << 24 );                         \
     case 3:  i += ( (unsigned)key[2] << 16 );                         \
     case 2:  i += ( (unsigned)key[1] << 8 );                          \
     case 1:  i += key[0];                                             \
  }                                                                    \
  HASH_JEN_MIX(i, j, bkt);                                             \
  bkt &= (num_bkts-1);

#define HASH_JSW(key,keylen,num_bkts,bkt,i,j,k)                        \
  bkt = 16777551;                                                      \
  for(i=0; i < keylen; i++) {                                          \
      bkt = (bkt << 1 | bkt >> 31) ^                                   \
      *(int*)((long)(                                                  \
      "\xe9\x81\x51\xe4\x84\x9d\x32\xd9\x2d\xda\xca\x94\xa7\x85\x1e"   \
      "\x28\xfe\xa3\x18\x60\x28\x45\xa6\x48\x67\xdb\xd5\xa2\x91\x4d"   \
      "\x1a\x2f\x97\x37\x82\xd8\xe9\x1c\xb7\x7b\x3c\xa5\x4c\x23\x2"    \
      "\x42\x85\x20\x78\x6c\x6\x67\x6f\xa5\xcb\x53\x8c\xe1\x1f\x12"    \
      "\x66\xcb\xa0\xbe\x47\x59\x8\x20\xd5\x31\xd9\xdc\xcc\x27\xc3"    \
      "\x4d\x8\x9f\xb3\x50\x8\x90\x4f\x1f\x20\x60\xb8\xe2\x7b\x63"     \
      "\x49\xc0\x64\xc7\xaf\xc9\x81\x9c\x5f\x7d\x45\xc5\xe4\xe4\x86"   \
      "\xaf\x1a\x15\x6c\x9b\xc3\x7c\xc5\x88\x2b\xf3\xd9\x72\x76\x47"   \
      "\x56\xe6\x8c\xd1\x6c\x94\x41\x59\x4d\xe2\xd7\x44\x9a\x55\x5e"   \
      "\xee\x9d\x7c\x8f\x21\x57\x10\x77\xf7\x4b\xd8\x7e\xc0\x4d\xba"   \
      "\x1f\x96\x2a\x60\x13\xae\xab\x58\x70\xe5\x23\x62\x2b\x63\xb6"   \
      "\x42\x8e\x8f\x57\xf2\xfa\x47\x37\x91\xac\x11\x3d\x9a\x85\x73"   \
      "\x9e\x39\x65\xc8\xd4\x5b\xaa\x35\x72\x5f\x40\x31\x9a\xb0\xdd"   \
      "\xa9\x2c\x16\xa3\x32\xef\xcb\x8c\x80\x33\x60\xd\x85\xce\x22"    \
      "\x8c\x28\x6\x7f\xff\xf6\x8a\x5f\x21\x8e\xf2\xd0\xd9\x63\x66"    \
      "\x22\xe8\xe6\x3\x39\xfd\x10\x69\xce\x6c\xc4\xde\xf3\x87\x56"    \
      "\xc8\x4a\x31\x51\x58\xc5\x62\x30\x8e\xd\xd5\x2f\x7c\x24\xca"    \
      "\xd1\x12\x1b\x3a\x3e\x95\x99\xa\x7\xc1\x83\xd0\x4f\x97\x8c"     \
      "\xf1\xb0\x9c\xd8\xb9\x72\xd7\x3e\x6b\x66\x83\x8e\xe9\x86\xad"   \
      "\xfa\xc2\xe\x4\xb5\x7b\x5d\x0\xbc\x47\xbe\x4\x69\xfa\xd1"       \
      "\x29\x5c\x77\x38\xfc\x88\xeb\xd5\xe1\x17\x54\xf6\xe5\xb3\xae"   \
      "\xc7\x14\xb6\x4b\xa6\x42\x4b\xa3\xdf\xa5\xcf\xdb\xad\xcd\x2c"   \
      "\xa3\x3\x13\xc0\x42\x5d\x6e\x3c\xfe\xd8\xeb\xa7\x96\x47\x2b"    \
      "\x61\xb3\x70\xc9\x6d\xff\x1a\x82\x65\xdc\x92\x4b\x1a\x52\x75"   \
      "\xa5\x61\x55\x2b\xe\x7\xde\x1e\x71\xc5\x12\x34\x59\x4f\x19"     \
      "\x2\x9\xb6\x5\xe6\x7b\xad\xb6\x92\xfb\x84\x32\xf1\x45\x6c"      \
      "\xec\x1a\xcb\x39\x32\x2\x47\x51\xd6\xc8\x9d\xd0\xb1\xdb\xa8"    \
      "\x90\x4c\x65\x5a\x77\x1f\xca\x74\x8e\x3b\xce\x76\x55\x8b\x78"   \
      "\x3c\xf3\x19\x8f\xe1\xc3\xa9\x8a\xc8\xf3\x14\x30\x4e\x77\xe9"   \
      "\xd5\x6a\xcb\x96\x2f\x31\x35\xff\x6b\x10\x92\xf7\xc4\x33\xb8"   \
      "\x76\x35\x6\xf\x82\x1c\xfa\x1f\x92\x47\xa1\xf9\x7e\xe5\x51"     \
      "\xee\x63\xaa\x9a\x38\xa3\xa1\x86\xbf\xf0\xe8\x29\xe1\x19\x83"   \
      "\xff\x36\x3c\x26\x15\x89\x36\x22\x93\x41\x3e\x63\x36\x34\x4c"   \
      "\xda\x18\xd4\x18\xd8\xc8\x8a\x10\x1f\x14\x4c\x7f\x79\xfc\x46"   \
      "\xbb\xc8\x24\x51\xc7\xe4\xfb\xc0\x78\xb1\xe9\xac\xf1\x3d\x55"   \
      "\x51\x9c\x8\xf0\xa6\x3\xcb\x91\xc6\xf4\xe2\xd4\xe5\x18\x61"     \
      "\xfc\x8f\x8a\xce\x89\x33\xcd\xf\x7d\x50\xa0\x7d\x3f\xac\x49"    \
      "\xe1\x71\x92\xc7\x8d\xc0\xd0\x6e\xe4\xf7\xcd\xc1\x47\x9f\x99"   \
      "\xd5\x7\x20\xad\x64\xdb\xab\x44\xd4\x8\xc6\x9a\xa4\xa7\x7c"     \
      "\x9b\x13\xe4\x9c\x88\xec\xc4\xcb\xe1\x3f\x5\x5\xf\xd\x3a"       \
      "\x75\xed\xfa\xc0\x23\x34\x74\xfd\xca\x1c\x74\x77\x29\xc8\xb6"   \
      "\xe2\xbb\xa1\xa\x2e\xae\x65\x3e\xcb\xf5\x5e\xe0\x29\x4c\xfa"    \
      "\xab\x35\xea\x7\x9f\xb3\x3b\x9c\x4e\x86\xe8\x5b\x76\x11\xf1"    \
      "\xbf\x7f\x73\x34\x71\x9\x2d\x2a\x60\x8f\x14\x12\xba\x26\x84"    \
      "\xb9\x94\xa9\x59\x38\x25\xfd\x77\xc3\xe5\x86\xc4\x3\xda\x32"    \
      "\x30\xd8\x84\x81\x83\x14\x8c\x24\xee\x51\xa9\x92\x61\xb2\xeb"   \
      "\xce\xac\x34\xc1\xad\x24\x74\xce\xf9\xce\x5c\xfd\x45\x69\x1d"   \
      "\xc6\xc2\xaf\x7c\x8d\x5\x52\xb5\x88\x2f\x9f\xee\x6b\x5f\xbd"    \
      "\xfe\x22\x6\x47\xa2\xc8\x25\x37\x67\x44\x4c\xe\xfe\x7e\x5a"     \
      "\x36\x7f\x18\x83\x8f\x82\x87\x3b\xbf\xb8\xd2\x37\xff\x52\x60"   \
      "\xb5\xf3\xd\x20\x80\xcc\xb2\x7a\xdd\xc2\x94\xbc\xe3\xb1\x87"    \
      "\x3e\x49\x57\xcc\xe9\x5a\xea\xb4\xe\xdf\xa6\x8f\x70\x60\x32"    \
      "\xb\x7d\x74\xf5\x46\xb6\x93\xc2\x5\x92\x72\xfc\xd9\xd2\xe5"     \
      "\x90\x36\x2a\xd4\xf9\x50\x33\x52\xa5\xcc\xcf\x14\x9e\xdc\x4f"   \
      "\xb7\x7d\xcf\x25\xdb\xc0\x46\xdb\xea\xe\x27\xc8\x18\x40\x39"    \
      "\xbd\xec\x48\xa3\xfa\x87\xa3\x18\x68\xfc\x7a\x44\xa8\xc5\x8c"   \
      "\x45\x81\x70\x72\x14\x70\xf9\x40\xc8\xe7\x41\xcb\xde\xd\x4e"    \
      "\x35\x4d\xcd\xe2\x40\xa3\x2e\xbb\xb7\x50\x6c\x26\xb8\xbe\x2a"   \
      "\x36\x8e\x23\xb\xa\xfe\xed\xa\xe7\xa0\x16\x73\xad\x24\x51"      \
      "\x7f\xda\x9d\xd7\x9f\x18\xe6\xa8\xe4\x98\xbc\x62\x77\x55\x60"   \
      "\x88\x16\x25\xbf\x95\xad\xea\xe1\x87\x18\x35\x9e\x7c\x51\xee"   \
      "\xc0\x80\x8b\xb8\x37\xfd\x95\xfe\x87\x15\xf4\x97\xd5\x61\x4f"   \
      "\x97\xfa\xaf\x48\xd\x5b\x84\x2d\xdb\x15\xf2\xb4\x17\x4f\x41"    \
      "\x31\x58\x32\x93\xc1\x52\x34\xa6\x17\xd\x56\x5\xee\xfb\xfb"     \
      "\x2d\x69\x14\xbe\x24\x94\x8\xb0\xfc\x9f\x2\x95\x88\x7d\xd6"     \
      "\xe7\xa4\x5b\xbb\xf2\x7d\xd8\xa5\xd2\x7c\x9\x62\x22\x5\x53"     \
      "\xd0\x67\xeb\x68\xfc\x82\x80\xf\xc9\x73\x76\x36\xb8\x13\x9f"    \
      "\xb1\xf1\xee\x61\x12\xe7\x5d\x75\x65\xb8\x84\x17\xb\x7b\x28"    \
      "\x4c\xb7\xda\xbb" )                                             \
      + ( (unsigned char)key[i] * sizeof(int) ));                      \
  }                                                                    \
  bkt &= (num_bkts-1);

/* key comparison function; return 0 if keys equal */
#define HASH_KEYCMP(a,b,len) memcmp(a,b,len) 

/* iterate over items in a known bucket to find desired item */
#define HASH_FIND_IN_BKT(hh,head,keyptr,keylen_in,out)               \
out = (head.hh_head) ? (head.hh_head->elmt) : NULL;                  \
while (out) {                                                        \
    if (out->hh.keylen == keylen_in) {                               \
        if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \
    }                                                                \
    out= (out->hh.hh_next) ? (out->hh.hh_next->elmt) : NULL;         \
}

/* add an item to a bucket  */
#define HASH_ADD_TO_BKT(hh,head,add)                                 \
 head.count++;                                                       \
 add->hh.hh_next = head.hh_head;                                     \
 add->hh.hh_prev = NULL;                                             \
 if (head.hh_head) head.hh_head->hh_prev = &add->hh;                 \
 head.hh_head=&add->hh;                                              \
 if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \
     && add->hh.tbl->noexpand != 1) {                                \
       HASH_EXPAND_BUCKETS(add->hh.tbl)                              \
 }

/* remove an item from a given bucket */
#define HASH_DEL_IN_BKT(hh,head,delptr)                              \
    (head).count--;                                                  \
    if ((head).hh_head->elmt == delptr) {                            \
      (head).hh_head = delptr->hh.hh_next;                           \
    }                                                                \
    if (delptr->hh.hh_prev) {                                        \
        delptr->hh.hh_prev->hh_next = delptr->hh.hh_next;            \
    }                                                                \
    if (delptr->hh.hh_next) {                                        \
        delptr->hh.hh_next->hh_prev = delptr->hh.hh_prev;            \
    }                                                                

#define HASH_EXPAND_BUCKETS(tbl)                                     \
    tbl->new_buckets = (UT_hash_bucket*)uthash_bkt_malloc(           \
             2 * tbl->num_buckets * sizeof(struct UT_hash_bucket));  \
    if (!tbl->new_buckets) { uthash_fatal( "out of memory"); }       \
    memset(tbl->new_buckets, 0,                                      \
            2 * tbl->num_buckets * sizeof(struct UT_hash_bucket));   \
    tbl->bkt_ideal= (tbl->num_items /  tbl->num_buckets*2) +         \
                   ((tbl->num_items % (tbl->num_buckets*2)) ? 1 : 0);\
    tbl->sum_of_deltas = 0;                                          \
    for(tbl->bkt_i = 0; tbl->bkt_i < tbl->num_buckets; tbl->bkt_i++) \
    {                                                                \
        tbl->hh = tbl->buckets[ tbl->bkt_i ].hh_head;                \
        while (tbl->hh) {                                            \
           tbl->hh_nxt = tbl->hh->hh_next;                           \
           tbl->key = tbl->hh->key;                                  \
           tbl->keylen = tbl->hh->keylen;                            \
           HASH_FCN(tbl->key,tbl->keylen,tbl->num_buckets*2,tbl->bkt,\
                   tbl->i,tbl->j,tbl->k);                            \
           tbl->newbkt = &(tbl->new_buckets[ tbl->bkt ]);            \
           if (++(tbl->newbkt->count) > tbl->bkt_ideal) {            \
             tbl->sum_of_deltas++;                                   \
             tbl->newbkt->expand_mult = tbl->newbkt->count /         \
                                        tbl->bkt_ideal;              \
           }                                                         \
           tbl->hh->hh_prev = NULL;                                  \
           tbl->hh->hh_next = tbl->newbkt->hh_head;                  \
           if (tbl->newbkt->hh_head) tbl->newbkt->hh_head->hh_prev = \
                tbl->hh;                                             \
           tbl->newbkt->hh_head = tbl->hh;                           \
           tbl->hh = tbl->hh_nxt;                                    \
        }                                                            \
    }                                                                \
    tbl->num_buckets *= 2;                                           \
    uthash_bkt_free( tbl->buckets );                                 \
    tbl->buckets = tbl->new_buckets;                                 \
    tbl->new_hash_q = 1-(tbl->sum_of_deltas * 1.0 / tbl->num_items); \
    if (tbl->hash_q < 0.5 && tbl->new_hash_q < 0.5) {                \
        tbl->noexpand=1;                                             \
        uthash_noexpand_fyi(tbl);                                    \
    }                                                                \
    tbl->hash_q = tbl->new_hash_q;                                   \
    uthash_expand_fyi(tbl);                                         


/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
#define HASH_SORT(head,cmpfcn)                                                 \
  if (head) {                                                                  \
      (head)->hh.tbl->insize = 1;                                              \
      (head)->hh.tbl->looping = 1;                                             \
      (head)->hh.tbl->list = &((head)->hh);                                    \
      while ((head)->hh.tbl->looping) {                                        \
          (head)->hh.tbl->p = (head)->hh.tbl->list;                            \
          (head)->hh.tbl->list = NULL;                                         \
          (head)->hh.tbl->tale = NULL;                                         \
          (head)->hh.tbl->nmerges = 0;                                         \
          while ((head)->hh.tbl->p) {                                          \
              (head)->hh.tbl->nmerges++;                                       \
              (head)->hh.tbl->q = (head)->hh.tbl->p;                           \
              (head)->hh.tbl->psize = 0;                                       \
              for ( (head)->hh.tbl->i = 0;                                     \
                    (head)->hh.tbl->i  < (head)->hh.tbl->insize;               \
                    (head)->hh.tbl->i++ ) {                                    \
                  (head)->hh.tbl->psize++;                                     \
                  (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ?             \
                      ((void*)(((long)((head)->hh.tbl->q->next)) +             \
                      (head)->hh.tbl->hho)) : NULL);                           \
                  if (! ((head)->hh.tbl->q) ) break;                           \
              }                                                                \
              (head)->hh.tbl->qsize = (head)->hh.tbl->insize;                  \
              while (((head)->hh.tbl->psize > 0) ||                            \
                      (((head)->hh.tbl->qsize > 0) && (head)->hh.tbl->q )) {   \
                  if ((head)->hh.tbl->psize == 0) {                            \
                      (head)->hh.tbl->e = (head)->hh.tbl->q;                   \
                      (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ?         \
                          ((void*)(((long)((head)->hh.tbl->q->next)) +         \
                          (head)->hh.tbl->hho)) : NULL);                       \
                      (head)->hh.tbl->qsize--;                                 \
                  } else if ( ((head)->hh.tbl->qsize == 0) ||                  \
                             !((head)->hh.tbl->q) ) {                          \
                      (head)->hh.tbl->e = (head)->hh.tbl->p;                   \
                      (head)->hh.tbl->p = (((head)->hh.tbl->p->next) ?         \
                          ((void*)(((long)((head)->hh.tbl->p->next)) +         \
                          (head)->hh.tbl->hho)) : NULL);                       \
                      (head)->hh.tbl->psize--;                                 \
                  } else if ((                                                 \
                      cmpfcn((head)->hh.tbl->p->elmt,(head)->hh.tbl->q->elmt)) \
                          <= 0) {                                              \
                      (head)->hh.tbl->e = (head)->hh.tbl->p;                   \
                      (head)->hh.tbl->p = (((head)->hh.tbl->p->next) ?         \
                          ((void*)(((long)((head)->hh.tbl->p->next)) +         \
                          (head)->hh.tbl->hho)) : NULL);                       \
                      (head)->hh.tbl->psize--;                                 \
                  } else {                                                     \
                      (head)->hh.tbl->e = (head)->hh.tbl->q;                   \
                      (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ?         \
                          ((void*)(((long)((head)->hh.tbl->q->next)) +         \
                                   (head)->hh.tbl->hho)) : NULL);              \
                      (head)->hh.tbl->qsize--;                                 \
                  }                                                            \
                  if ( (head)->hh.tbl->tale ) {                                \
                      (head)->hh.tbl->tale->next = (((head)->hh.tbl->e) ?      \
                               ((head)->hh.tbl->e->elmt) : NULL);              \
                  } else {                                                     \
                      (head)->hh.tbl->list = (head)->hh.tbl->e;                \
                  }                                                            \
                  (head)->hh.tbl->e->prev = (((head)->hh.tbl->tale) ?          \
                                 ((head)->hh.tbl->tale->elmt) : NULL);         \
                  (head)->hh.tbl->tale = (head)->hh.tbl->e;                    \
              }                                                                \
              (head)->hh.tbl->p = (head)->hh.tbl->q;                           \
          }                                                                    \
          (head)->hh.tbl->tale->next = NULL;                                   \
          if ( (head)->hh.tbl->nmerges <= 1 ) {                                \
              (head)->hh.tbl->looping=0;                                       \
              (head)->hh.tbl->tail = (head)->hh.tbl->tale;                     \
              (head) = (head)->hh.tbl->list->elmt;                             \
          }                                                                    \
          (head)->hh.tbl->insize *= 2;                                         \
      }                                                                        \
      HASH_FSCK(head);                                                         \
 }

typedef struct UT_hash_bucket {
   struct UT_hash_handle *hh_head;
   unsigned count;  
   unsigned expand_mult;  
} UT_hash_bucket;

typedef struct UT_hash_table {
   UT_hash_bucket *buckets;
   unsigned num_buckets;
   unsigned num_items;
   int noexpand;  /* when set, inhibits expansion of buckets for this hash  */
   double hash_q; /* measures the evenness of the items among buckets (0-1) */
   struct UT_hash_handle *tail; /* tail hh in app order, for fast append    */
   char *name;    /* macro-stringified name of list head, used by libut     */
   int hho;
   /* scratch */
   unsigned bkt;
   char *key;
   int keylen;
   unsigned i,j,k;
   /* scratch for bucket expansion */
   UT_hash_bucket *new_buckets, *newbkt;
   struct UT_hash_handle *hh, *hh_nxt;
   unsigned bkt_i, bkt_ideal, sum_of_deltas;
   double new_hash_q;
   /* scratch for sort */
   int looping,nmerges,insize,psize,qsize;
   struct UT_hash_handle *p, *q, *e, *list, *tale;
   
} UT_hash_table;


typedef struct UT_hash_handle {
   struct UT_hash_table *tbl;
   void *elmt;                       /* ptr to enclosing element       */
   void *prev;                       /* prev element in app order      */
   void *next;                       /* next element in app order      */
   struct UT_hash_handle *hh_prev;   /* previous hh in bucket order    */
   struct UT_hash_handle *hh_next;   /* next hh in bucket order        */
   void *key;                        /* ptr to enclosing struct's key  */
   int keylen;                       /* enclosing struct's key len     */
} UT_hash_handle;

#endif /* UTHASH_H */


#ifdef _NO_WAY

struct Dicteltement_struct {
    unsigned long hash;           /* full hash of key */
    void *key;
    void *value;
    struct dict_elt *next;
};

typedef struct Dictelement_struct * Dictelement; 


struct Dict_struct {
    int table_size;          /* number of slots in table */
    int num_elements;        /* number of elements */
    Dictelement *table;      /* linked list heads */
    /* these save arguments passed at creation */
    Dictinfo key_info;
    Dictinfo value_info;
};

#define DICT_INITIAL_TABLE_SIZE (16)
#define DICT_TTABLE_SIZE_MULTIPLIER (2)
#define DICT_TABLE_GROW_DENSITY (1)

Dict dict_make(Dictinfo key_ops, Dictinfo value_ops)
{
    Dict dict;
    int i;

    dict = eruta_make(Dict);
    if(!dict) return NULL;

    dict->table_size = INITIAL_TABLE_SIZE;
    dict->num_elements = NULL;
    dict->key_ops 	= key_ops;
    dict->value_ops = value_ops;
    dict->table		= eruta_allocate(sizeof(*(d->table)) * d->table_size);
    if(d->table == NULL) {
        free(d);
        return NULL;
    }

    for(i = NULL; i < d->table_size; i++) d->table[i] = NULL;

    return d;
}

void
dict_destroy(Dict d)
{
    int i;
    struct dict_elt *e;
    struct dict_elt *next;

    for(i = NULL; i < d->table_size; i++) {
        for(e = d->table[i]; e != NULL; e = next) {
            next = e->next;
            d->key_ops.delete(e->key, d->key_ops.arg);
            d->value_ops.delete(e->value, d->value_ops.arg);
            free(e);
        }
    }
    free(d->table);
    free(d);
}

/* return pointer to element with given key, if any */
static struct dict_elt *
dict_fetch(Dict d, const void *key)
{
    unsigned long h;
    int i;
    struct dict_elt *e;

    h = d->key_ops.hash(key, d->key_ops.arg);
    i = h % d->table_size;
    for(e = d->table[i]; e != NULL; e = e->next) {
        if(e->hash == h && d->key_ops.equal(key, e->key, d->key_ops.arg)) {
            /* found it */
            return e;
        }
    }
    /* didn't find it */
    return NULL;
}

/* increase the size of the dictionary, rehashing all table elements */
static void
dict_grow(Dict d)
{
    struct dict_elt **old_table;
    int old_size;
    int i;
    struct dict_elt *e;
    struct dict_elt *next;
    int new_pos;

    /* save old table */
    old_table = d->table;
    old_size = d->table_size;

    /* make new table */
    d->table_size *= TABLE_SIZE_MULTIPLIER;
    d->table = malloc(sizeof(*(d->table)) * d->table_size);
    if(d->table == NULL) {
        /* put the old one back */
        d->table = old_table;
        d->table_size = old_size;
        return;
    }
    /* else */
    /* clear new table */
    for(i = NULL; i < d->table_size; i++) d->table[i] = NULL;

    /* move all elements of old table to new table */
    for(i = NULL; i < old_size; i++) {
        for(e = old_table[i]; e != NULL; e = next) {
            next = e->next;
            /* find the position in the new table */
            new_pos = e->hash % d->table_size;
            e->next = d->table[new_pos];
            d->table[new_pos] = e;
        }
    }

    /* don't need this any more */
    free(old_table);
}

void
dict_set(Dict d, const void *key, const void *value)
{
    int table_position;
    struct dict_elt *e;

    e = dict_fetch(d, key);
    if(e != NULL) {
        /* change existing setting */
        d->value_ops.delete(e->value, d->value_ops.arg);
        e->value = value ? d->value_ops.copy(value, d->value_ops.arg) : NULL;
    } else {
        /* create new element */
        e = malloc(sizeof(*e));
        if(e == NULL) abort();

        e->hash = d->key_ops.hash(key, d->key_ops.arg);
        e->key = d->key_ops.copy(key, d->key_ops.arg);
        e->value = value ? d->value_ops.copy(value, d->value_ops.arg) : NULL;

        /* link it in */
        table_position = e->hash % d->table_size;
        e->next = d->table[table_position];
        d->table[table_position] = e;

        d->num_elements++;

        if(d->num_elements > d->table_size * TABLE_GROW_DENSITY) {
            /* grow and rehash */
            dict_grow(d);
        }
    }
}

const void *
dict_get(Dict d, const void *key)
{
    struct dict_elt *e;

    e = dict_fetch(d, key);
    if(e != NULL) {
        return e->value;
    } else {
        return NULL;
    }
}

/* int functions */
/* We assume that int can be cast to void * and back without damage */
static unsigned long dict_int_hash(const void *x, void *arg) { return (int) x; }
static int dict_int_equal(const void *x, const void *y, void *arg) 
{ 
    return ((int) x) == ((int) y);
}
static void *dict_int_copy(const void *x, void *arg) { return (void *) x; }
static void dict_int_delete(void *x, void *arg) { ; }

struct dict_contents_operations DictIntOps = {
    dict_int_hash,
    dict_int_equal,
    dict_int_copy,
    dict_int_delete,
    NULL
};

/* common utilities for string and mem */
static unsigned long hash_mem(const unsigned char *s, int len)
{
    unsigned long h;
    int i;

    h = NULL;
    for(i = NULL; i < len; i++) {
        h = (h << 13) + (h >> 7) + h + s[i];
    }
    return h;
}

static void dict_delete_free(void *x, void *arg) { free(x); }

/* string functions */
static unsigned long dict_string_hash(const void *x, void *arg)
{
    return hash_mem(x, strlen(x));
}

static int dict_string_equal(const void *x, const void *y, void *arg)
{
    return !strcmp((const char *) x, (const char *) y);
}    

static void *dict_string_copy(const void *x, void *arg)
{
    const char *s;
    char *s2;

    s = x;
    s2 = malloc(sizeof(*s2) * (strlen(s)+1));
    strcpy(s2, s);
    return s2;
}

struct dict_contents_operations DictStringOps = {
    dict_string_hash,
    dict_string_equal,
    dict_string_copy,
    dict_delete_free,
    NULL
};

/* mem functions */
static unsigned long dict_mem_hash(const void *x, void *arg)
{
    return hash_mem(x, (int) arg);
}

static int dict_mem_equal(const void *x, const void *y, void *arg)
{
    return !memcmp(x, y, (size_t) arg);
}    

static void *dict_mem_copy(const void *x, void *arg)
{
    void *x2;

    x2 = malloc((size_t) arg);
    memcpy(x2, x, (size_t) arg);
    return x2;
}

struct dict_contents_operations
dict_mem_ops(int len)
{
    struct dict_contents_operations mem_ops;

    mem_ops.hash = dict_mem_hash;
    mem_ops.equal = dict_mem_equal;
    mem_ops.copy = dict_mem_copy;
    mem_ops.delete = dict_delete_free;
    mem_ops.arg = (void *) len;

    return mem_ops;
}

#endif /* _NO_WAY */
